package dmsxl.erchashu;

import java.util.*;

/**
 * Author: Zhang Dongwei
 * Date: 2023/5/20 16:57
 * 二叉搜索树中的众数
 */
public class ecs25_501 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(5);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(6);
        TreeNode node4 = new TreeNode(2);
        TreeNode node5 = new TreeNode(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node3.left = node5;
        System.out.println(Arrays.toString(findMode(node1)));
    }

//    自己写的，效果很差
    public static int[] findMode1(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        getmap(root, map);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            if (value > max){
                max = value;
            }
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            if (value == max){
                list.add(key);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }

    public static void getmap(TreeNode root, HashMap map){
        if (root == null) return;
        getmap(root.left, map);
        if (!map.containsKey(root.val)){
            map.put(root.val, 1);
        }else {
            map.put(root.val, (int)map.get(root.val) + 1);
        }
        getmap(root.right, map);
    }

//    自己写的，稍微精简一点,效果好一点，但不明显
    public static int[] findMode(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> list = new ArrayList<>();
        int max = Integer.MIN_VALUE;
        getmap(root, map);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            if (value > max){
                max = value;
                list = new ArrayList<>();
                list.add(key);
            } else if (value == max){
                list.add(key);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }
        return res;
    }
}
